/*
 * arvore.c
 *
 *  Created on: 25/04/2011
 *      Author: joao
 */

#include <stdio.h>
#include <stdlib.h>

#include "arvore.h"

int ehAVL(int *isavl, no **p){
	int esq=0, dir=0, dif;

	if((*p)->esq!=NULL){
		esq = 1 + ehAVL(isavl, &(*p)->esq);
	}

	if((*p)->dir!=NULL){
		dir = 1 + ehAVL(isavl, &(*p)->dir);
	}

	//é AVL?
	dif = esq - dir;
	if(dif==0 || dif==-1 || dif==1)
		*isavl = *isavl;
	else
		*isavl = 0;

	//retorna tamanho
	if(esq>dir)
		return esq;
	else
		return dir;

	return 0;
}

int tahBalanceado(int *bal, no **p){
	int esq=0, dir=0;

	if((*p)->esq!=NULL){
		esq = 1 + tahBalanceado(bal, &(*p)->esq);
	}

	if((*p)->dir!=NULL){
		dir = 1 + tahBalanceado(bal, &(*p)->dir);
	}

	//tah bal
	if((dir-esq)==(*p)->bal)
		*bal = *bal;
	else
		*bal = 0;

	//retorna tamanho
	if (esq > dir)
		return esq;
	else
		return dir;

	return 0;
}


int insereAVL(int x, no **p) {
	int cresceu;

	/* Se a arvore esta vazia insere. */
	if (*p == NULL) {
		*p = (no *) malloc(sizeof(no));
		(*p)->info = x;
		/* Caso houvesse outros dados eles deveriam ser copiados aqui. */
		(*p)->dir = (*p)->esq = NULL;
		/* Balanceamento de uma folha e sempre perfeito */
		(*p)->bal = 0;
		/* Esta sub arvore cresceu */
		cresceu = 1;
	}
	/* Senao verifica se tem que inserir a esquerda */
	else if ((*p)->info > x) {
		/* Tenta inserir a esquerda e ve se a sub-arvore cresceu */
		cresceu = insereAVL(x, &(*p)->esq);
		if (cresceu) {
			/* Verifica o estado atual de balanceamento */
			switch ((*p)->bal) {
			/* Se a arvore dir. era maior nao ha crescimento*/
			case 1:
				(*p)->bal = 0;
				cresceu = 0;
				break;
				/* Se a arvore dir. tinha tamanho igual, houve crescimento*/
			case 0:
				(*p)->bal = -1;
				cresceu = 1;
				break;
				/* Se a sub-arvore da esq. ja era maior, deve-se re-balancear.*/
			case -1:
				/* Verifica qual o caso de re-balanceamento.*/
				/* Se a arvore da esquerda do filho da esquerda esta mais*/
				/* alta basta uma rotacao para direita.*/
				if ((*p)->esq->bal == -1) {
					/* Rotacao para direita.
					 */
					rot_dir(p);
					/* Acerta os balanceamentos. */
					(*p)->bal = (*p)->dir->bal = 0;
				} else {
					/* Rotacao dupla.*/
					/* Primeiro a esquerda.*/
					rot_esq(&(*p)->esq);
					/* Depois a direita.*/
					rot_dir(p);
					/* Acerta balanceamentos. */
					if ((*p)->bal == -1) {
						(*p)->esq->bal = 0;
						(*p)->dir->bal = 1;
					} else {
						(*p)->dir->bal = 0;
						(*p)->esq->bal = -(*p)->bal;
					}
					(*p)->bal = 0;
				}
				cresceu = 0;
			}
		}
	}
	/* Verifica se tem que inserir a direita. */
	else if ((*p)->info < x) {
		/* Tenta inserir a direita e ve se a sub-arvore cresceu */
		cresceu = insereAVL(x, &(*p)->dir);
		if (cresceu) {
			/* Verifica o estado atual de balanceamento */
			switch ((*p)->bal) {
			/* Se a arvore esq. era maior nao ha crescimento*/
			case -1:
				(*p)->bal = 0;
				cresceu = 0;
				break;
				/* Se a arvore esq. tinha tamanho igual, houve crescimento*/
			case 0:
				(*p)->bal = 1;
				cresceu = 1;
				break;
				/* Se a arvore da dir. ja era maior, deve-se re-balancear.*/
			case 1:
				/* Verifica qual o caso de re-balanceamento.*/
				/* Se a arvore da direita do filho da direita esta mais*/
				/* alta basta uma rotacao para esquerda.*/
				if ((*p)->dir->bal == 1) {
					/* Rotacao para esquerda.*/

					rot_esq(p);
					/* Acerta os balanceamentos. */
					(*p)->bal = (*p)->esq->bal = 0;
				} else {
					/* Rotacao dupla.
					 */
					/* Primeiro a direita.
					 */
					rot_dir(&(*p)->dir);
					/* Depois a esquerda.
					 */
					rot_esq(p);
					/* Acerta balanceamentos. */
					if ((*p)->bal == -1) {
						(*p)->esq->bal = 0;
						(*p)->dir->bal = 1;
					} else {
						(*p)->dir->bal = 0;
						(*p)->esq->bal = -(*p)->bal;
					}
					(*p)->bal = 0;
				}
				cresceu = 0;
			}
		}
	} else
		cresceu = 0;
	return cresceu;
}


void insereBalanceado(int menor, int maior, no **raiz){
	int metade;

	if(menor==maior)
		BuscaInsere(menor, raiz);
	else{
		metade=(maior+menor)/2;
		BuscaInsere(metade, raiz);
		insereBalanceado(menor,metade-1,raiz);
		insereBalanceado(metade+1,maior,raiz);
	}

}

 /*Rotacao a direita */

void rot_dir(no **p) {
/*  no *aux;
  aux = (*p)->esq;
  (*p)->esq = aux->dir;
  aux->dir = *p;

  (*p)->n_elem =

  *p = aux;*/
	  no *aux;
	  aux = (*p)->esq;
	  (*p)->esq = aux->dir;
	  aux->dir = *p;

	  *p = aux;
}

/* Rota��o � esquerda */

void rot_esq(no **p) {
	  no *aux;
	  aux = (*p)->dir;
	  (*p)->dir = aux->esq;
	  aux->esq = *p;

	  *p = aux;
/*  no *aux;
  aux = (*p)->dir;
  (*p)->dir = aux->esq;
  aux->esq = *p;

  (*p)->n_elem = (*p)->n_elem - aux->n_elem;
  if((*p)->dir != NULL)
	  (*p)->n_elem += ((*p)->dir)->n_elem;

  aux->n_elem = aux->n_elem + (*p)->n_elem;
  if((*p)-> != NULL)
	  aux->n_elem -= ((*p)->dir)->n_elem;

  *p = aux;*/
}

void insere_topo(int x, no **p) {
  /* Se a arvore esta vazia e facil inserir no topo */
  if (*p == NULL) {
    *p = (no *) malloc(sizeof(no));
    (*p)->info = x;

    /* Caso houvesse mais dados, copie-os aqui. */
    (*p)->dir = (*p)->esq = NULL;
  }
  else {
    if (x < (*p)->info) {
      insere_topo(x, &(*p)->esq);
      rot_dir(p);
    }
    else if (x > (*p)->info) {
      insere_topo(x, &(*p)->dir);
      rot_esq(p);
    }
  }
}


no *selecao(int k, no *raiz) {
  int t;

  /* Pode ser que o k-esimo elemento nao exista. */
  if (raiz->n_elem < k) return NULL;
  t = (raiz->esq == NULL) ? 0 : raiz->esq->n_elem;
  if (k < t + 1)
    return selecao(k, raiz->esq);
  if (k > t + 1)
    return selecao(k-t-1, raiz->dir);
  return raiz;
}

void sobe_menor(no **p) {
  if ((*p)->esq != NULL) {
    sobe_menor(&(*p)->esq);
    rot_dir(p);
  }
}

no *une_dir_esq(no *e, no **d) {
  /* Se a sub-arvore a direita eh vazia, retorna a outra. */
  if (*d == NULL) return e;
  sobe_menor(d);
  (*d)->esq = e;
  return *d;
}

void remove_no(int x, no **p) {
  no *aux;
  /* Verifica se o item esta na arvore. */
  if (*p == NULL) return;
  if (x < (*p)->info)
    remove_no(x, &(*p)->esq);
  if (x > (*p)->info)
    remove_no(x, &(*p)->dir);

  if (x == (*p)->info) {
    aux = *p;
    *p = une_dir_esq((*p)->esq, &(*p)->dir);
    free(aux);
  }
}

//aula passada

void P(no *p){
	printf("%d ", p->info);
}

void pre_ordem(no *raiz){
	if (raiz != NULL) {
		P(raiz);
		pre_ordem(raiz->esq);
		pre_ordem(raiz->dir);
	}
}

void in_ordem(no *raiz){
	if (raiz != NULL) {
		in_ordem(raiz->esq);
		P(raiz);
		in_ordem(raiz->dir);
	}
}

void pos_ordem(no *raiz){
	if(raiz != NULL){
		pos_ordem(raiz->esq);
		pos_ordem(raiz->dir);
		P(raiz);
	}
}

no  *busca(Tipo x, no *raiz){
	no *atual = raiz;

	while ((atual != NULL) && (atual->info != x))
    	if (x > atual->info) atual = atual->dir;
        else atual = atual->esq;
	return atual;
}


void BuscaInsere(Tipo x, no **p) {

	if (*p == NULL) { /* se o elemento nao foi encontrado, insere */
		*p = (no *) malloc(sizeof(no));
		(*p)->info = x;
		(*p)->esq = (*p)->dir = NULL;
		(*p)->cont = 1;
	} else if (x < (*p)->info){

		BuscaInsere(x, &((*p)->esq));
	}

	else if (x > (*p)->info)
		BuscaInsere(x, &((*p)->dir));
	else if (x == (*p)->info)
		(*p)->cont++;
}

int arrumaAVLEsquerda(no **p){
	if ((*p)->esq->bal == -1){
		rot_dir(p);
		(*p)->bal = (*p)->dir->bal = 0;
	} else{
		rot_esq(&(*p)->esq);
		rot_dir(p);
		if((*p)->bal == -1){
			(*p)->esq->bal = 0;
			(*p)->dir->bal = 1;
		} else {
			(*p)->dir->bal = 0;
			(*p)->esq->bal = -(*p)->bal;
		}
	}
	return 0;
}

int arrumaAVLDireita(no **p){
	if ((*p)->dir->bal == 1){
		rot_esq(p);
		(*p)->bal = (*p)->esq->bal = 0;
	}
	return 0;
}

/*int insereAVL(Tipo x, no **p) {
	int cresceu;

	if (*p == NULL) {  se o elemento nao foi encontrado, insere
		*p = (no *) malloc(sizeof(no));
		(*p)->info = x;
		(*p)->esq = (*p)->dir = NULL;
		(*p)->cont = 1;
		(*p)->bal = 0;

		cresceu = 1;
	} else if (x < (*p)->info){
		(*p)->n_elem++;
		cresceu = insereAVL(x, &((*p)->dir));
		if (cresceu){
			switch((*p)->bal){
			case1:


			break;
			case 0:


			break;
			}
		}
	}
	else if (x > (*p)->info){
		(*p)->n_elem++;
		BuscaInsere(x, &((*p)->dir));
	}
	else if (x == (*p)->info)
		(*p)->cont++;

	return cresceu;
}*/

/*void iniciaNovoNo (no **p){
	*p = (no *)malloc(sizeof(no));

	//(*p)->info = x;
	(*p)->esq = (*p)->dir = NULL;
	(*p)->cont = 1;
}*/

void imprime(no *raiz, int nivel) {
	/* Esta rotina e adequada para imprimir arvores com info de */
	/* comprimento maximo igual a 6 */
	int i;

	if (raiz == NULL) return;

	imprime(raiz->dir, nivel+1);

	for(i = 0; i < nivel; i++)
		printf("	");
	printf("%6d\n", raiz->info);

	imprime(raiz->esq, nivel+1);
}

void imprimeArquivo(no *raiz, FILE *saida) {
	/* Esta rotina e adequada para imprimir arvores com info de */
	/* comprimento maximo igual a 6 */


	if (raiz == NULL) return;

	imprimeArquivo(raiz->esq, saida);
	fprintf(saida, "%d %d\n", raiz->info, raiz->cont);
	imprimeArquivo(raiz->dir, saida);

}
